Diskussion:Lineare Optimierung

Fehlerberichtigung

Das diskrete lineare Optimierungsproblem ist KEIN SPEZIALFALL des Linearen Optimierungsproblems (obwohl man das vom Namen her denken könnte); dieser Teil des Artikels kann nicht so stehen bleiben. Viele Eigenschaften von linearean Optimierungsaufgaben sind für diskrete lineare Optimierungsaufgaben NICHT gültig. --Heinrich Puschmann (Diskussion) 14:59, 29. Aug. 2013 (CEST)

Sollte man dann vielleicht "verwandt" benutzen und - kurz - erklären, warum es eben kein Spezialfall ist?! Anhand eines Beispiels / Eigenschaft --mirer 17:38, 17. Sep 2004 (CEST)

Diskrete Optimierung ist KEIN Spezialfall von Linearer Optimierung, weil der inzwischen fest geprägte Fachausdruck "Lineare Optimierung" (auch "Lineare Programmierung") stillschweigend voraussetzt, dass beliebige reellzahlige Lösungen zulässig sind; was ja bei der diskreten Optimierung gerade NICHT der Fall ist.

Die DISKRETE OPTIMIERUNG ist wichtig genug, um eine eigenen Wikipedia-Artikel zu verdienen. Man könnte sie in lineare und nichtlineare diskrete Optimierung unterteilen, obwohl fast nur die lineare diskrete Optimierung in der Fachliteratur erwähnt wird. Dieser Tatbestand, und der englische Ausdruck "integer linear programming", mögen einige Laien dazu verleiten, sie fälschlicherweise für einen Spezialfall der Linearen Optimierung zu halten.

Ein wichtiger Sonderfall der linearen diskreten Optimierung sind DIOPHANTISCHE GLEICHUNGSSYSTEME, welche ebenfalls einen eigenen Artikel haben sollten.

Ich habe (als Erste-Hilfe-Maßnahme) die fehlerhaften Aussagen erst einmal berichtigt, aber für die stilistisch notwendige Umstrukturierung fehlen mir die Wikipedia-Kenntnisse. --Heinrich Puschmann (Diskussion) 14:59, 29. Aug. 2013 (CEST)

Die Bedingung $Ax\leq b$ ist komponentenweise zu verstehen, also als $a_{i}^{T}x=\sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}$

Wieso wird der Vektor $a_{i}$ transponiert. Es ist doch schon ein Zeilenvektor

Oma-Problem

Wir haben hier nicht nur ein travelling-salesman-Problem, sondern vor allem ein ausgewachsenes Oma-Problem. Vielleicht könnte man das Ganze doch ein bisschen nachvollziehbarer formulieren! --Philipendula 12:11, 5. Sep 2004 (CEST)

Was bedeutet der Ausdruck "Oma-Problem"? Ich kannte ihn nicht, und in der Wikipedia steht nichts darüber.

In Wikipedia:Wie schreibe ich gute Artikel Absatz 2, ist kurz was zur Verständlichkeit von Artikeln geschrieben. Generell sollte es halt so sein, dass ein neuer Artikel in der Einleitung so geschrieben ist, dass auch "jede Oma" bgreift, was z.B. die Relativitätstheorie ist. Evtl. lege ich die neuen gewünschten Artikel an ... mal schauen, ob ich da noch durchsteige ;) --mirer 20:58, 20. Sep 2004 (CEST)

mögliche Erweiterung

Meines Erachtens müsste der Eintrag noch dahingehend verändert werden, dass die Dualität von linearen Programmen dargestellt werden müsste. Ich selbst sehe mich aber ausserstande, dass kurz und formal präzisse anzustellen.

Lesenswert-Diskussion vom 8. Oktober

Hier noch die ausführliche Begründung für mein contra bei der Lesenswert-Diskussion, mit Vorschlägen zur Verbesserung:

• Wie oben schon bemerkt, fehlt die Dualität, die bei Linearen Programmen wichtig ist.
• Vieles, was im Simplexalgorithmus steht, gehört eigentlich hierher, insbesondere die Definition des Problems, das Bild und das Beispiel. Die beziehen sich allgemein auf Lineare Programmierung. Beim Simplexalgorithmus könnte man diese Teil dann nur nochmal kurz zusammenfassen, für Details auf die Lineare Optimierung verweisen und sich wirklich auf den Simplexalgorithmus konzentrieren.
• Der Text ist zum großen Teil gar nicht schlecht, aber die Struktur ist noch suboptimal. Vorschlag für eine Umstrukturierung des Artikels:
  • Einleitung (Begriffsdefinition, Einordnung, Bedeutung in der Praxis, Anwendungen erwähnen)
  • Geschichte der Linearen Programmierung
  • Anwendungen, (ausführlicher als jetzt, auch Bedeutung als Unterproblem beim Lösen ganzzahliger linearer Programme stärker herausstellen)
  • Problemdefinition und geometrische Interpretation (aus dem Simplexalgorithmus, Bild eines Polyeders mit einer Zielfunktion, Verweis auf Polyeder und Polytop (Geometrie),die auch überarbeitet werden müssten... ;-))
  • Lösbarkeit (auch aus algorithmischer Sicht oder nur aus theoretischer Sicht? Letztere kann man gut am Bild erklären.)
  • Dualität (was ist das, wozu ist das gut, aber nicht beliebig detailliert)
  • Lösungsverfahren (Simplexverfahren, Ellipsoidmethode, Innere-Punkte-Verfahren) kurz zusammenfassen (am Polyeder-Bild?) und auf die entsprechden Hauptartikel verweisen, dabei auch die Normalformen und algorithmische Komplexität unterbringen
  • (gemischt-)ganzzahlige lineare Programmierung: auf jeden Fall kurze Erwähnung mit praktischem Beispiel zur Abgrenzung. Bei den Algorithmen bin ich mir nicht sicher, ob wir die hier abhandeln sollten oder ob ein eigener Artikel Ganzzahlige lineare Optimierung besser wäre. Im Moment tendiere ich zu letzterem; der Artikel könnte ein guter Knotenpunkt sein für die Artikel aus der Serie Branch and Bound, Schnittebenenverfahren, TSP, usw.
• Die Anwendungen und die Geschichte kann man dabei sicherlich noch hin- und herschieben; die könnten evtl. auch ans Ende. Die Dualität könnte auch hinter die Lösungsverfahren.
• Insgesamt kann der Artikel mehr Anwendung und Bilder gebrauchen (Stichwort Oma). Am Bild eines Polytops mit einer Zielfunktion lassen sich auch viele Dinge prima ohne viele Formeln, aber trotzdem exakt, erklären. Nur bei der Dualität hört es auf...

Soweit mein Vorschlag; was haltet ihr davon? Ich bin auch gerne bereit, bei der Überarbeitung mitzumachen. -- Sdo 02:06, 10. Okt 2005 (CEST)

Lesenswert-Diskussion

Mit der Zufallsartikelsuche entdeckt. Scheint mir als absolutem Mathe-Idioten gar nicht mal so schlecht: Alles ist klar dargestellt, auch grafisch, vollständig, Literatur drin... Jesusfreund 03:39, 8. Okt 2005 (CEST)

• klares  Kontra - viele Formeln ersetzen keine verständliche Erläuterung. Das Simplex-Verfahren und das Problem des Handlungsreisenden könnten als lesenswerte Artikel durchgehen, wenn sie ein wenig überarbeitet werden. Der Übersichtsartikel Lineare Optimierung ist hingegen unzureichend. Unverständliche Einleitung, keine Grafik (obwohl graphische Lösungen das verständlichere Lösungsverfahren darstellen) und nur ein Anwendungsbeispiel, obwohl jeder BWL-Student im Grundstudium mindestens fünf Anwendungsbeispiele pauken muss. Ein Fall für den Focus. --Kapitän Nemo 11:21, 8. Okt 2005 (CEST)

•  Kontra – aus den gleichen und weiteren Gründen. Eine graphische Lösung könnte m.E. durchaus rein (z.B. das Bild aus dem Simplex-Algorithmus), solange klar wird, dass es sich um ein didaktisch wertvolles, aber aus praktischer Sicht irrelevantes Verfahren handelt. Die Struktur des Artikels ist überarbeitungsbedürftig, und die Anwendungsbeispiele sollten erweitert werden. Die Lösungsverfahren für ganzzahlige lineare Programme enthalten auch ein paar fragwürdige Aussagen (sind Gröbnerbasen wirklich so toll?) und müssen überarbeitet werden. Der Abschnitt über TSP klingt so, als sei das Schweden-TSP nur mit Hilfe von cutting planes gelöst worden, was nicht stimmt [1]. Ausserdem fehlt im Artikel ein geschichtlicher Abschnitt. Ich kann auch gerne mithelfen, die Lineare Optimierung, das TSP und den Simplexalgorithmus weiter zu verbessern – ich habe diese Artikel schon länger auf meiner todo-Liste, bin aber bisher noch nicht dazu gekommen. -- Sdo 16:26, 9. Okt 2005 (CEST)

Ich hab erstmal den Superlativ aus den Gröbnerbasen rausgenommen. Grothey 12:32, 12. Jan 2006 (CET)

•  Kontra Viel zu mathematisch, gerade ein zwei BWL-Beispiele fehlen. Zudem kann ich keine Grafiken finden - hat die inzwischen jemand entfernt? --Thetawave 12:48, 15. Okt 2005 (CEST)

Dualität

An Sdo: Die (korrigierten) Aussagen über Beschränktheit/Zulässigkeit von primalen/dualen Problemen waren schlichtweg falsch, ich habe die Ursprungsversion wiederhergetsellt. Ich meine man braucht $y\leq 0$ so wie das Problem da steht. Nicht sicher ob der schwache Dualitätssatz sinnvoll hier ist, er ist eigentlich nur eine Abschwächung der starken Dualität für den nichtkonvexen Fall. Ob das duale Problem mit oder ohne Schlupfvariablen geschrieben wird, wäre zu diskutieren. Ohne sieht es symmetrischer aus. Mit kann man versuchen eine Interpretation zu geben (z.B. über Schattenpreise) - ohne die Schlupfvariablen tauchen die Schattenpreise für $x\geq 0$ nur noch implizit auf. Ich lasse diese Punkte erstmal unverändert bis ich die Interpretation vernünftig aufgeschrieben bekomme. Grothey 10:24, 17. Jan 2006 (CET)

Hallo Grothey, so wie es da jetzt steht, stimmt es nicht. Der Zusatz mit den unendlichen Werten ist gut, den hatte ich vergessen. Aber wenn das primale LP unzulässig ist, muss das duale LP nicht unbeschränkt sein, sondern kann auch unzulässig sein. Als Beispiel betrachte das LP

$\min \;x+y\;s.t.\;x-y\leq 1,\;-x+y\leq 1,\;x,y\geq 0$.

Dieses LP ist unzulässig, und das duale LP ist gleich dem primalen, also auch unzulässig. Und es muss ganz klar $y\geq 0$ sein. Das ist die Version der Dualisierung, die ich mir merken kann und auf die ich immer alles zurückführe: nur nichtnegative Variablen, im primalen Maximieren mit $\leq$-Ungleichungen, im Dualen Minimieren mit $\geq$-Ungleichungen. Guck im Zweifelsfall nochmal irgendwo nach, aber ich bin mir da ziemlich sicher (u.a. steht es auch in der englischen Version so da).

Auf dem schwachen Dualitätssatz bestehe ich nicht unbedingt, aber ich fand ihn ganz sinnvoll, weil er Grundlage für alle Verfahren ist, die mit primalen und dualen Schranken arbeiten (u.a. Branch-and-Bound), und damit praktisch äußerst relevant. Die Schlupfvariablen hatte ich wegen der Symmetrie rausgenommen. Ohne weitere Erklärung der Schlupfvariablen war nicht einzusehen, warum das duale LP mit Schlupfvariablen da stehen sollte, das primale aber nicht. Wenn Du noch eine Interpretation mit Schattenpreisen dazuschreibst, habe ich auch nichts gegen die Schlupfvariablen einzuwenden.

Gruß, -- Sdo 11:37, 17. Jan 2006 (CET)

Hallo Sdo: Gut zu sehen dass noch jemand an der Optimierung sitzt. $y\geq 0$ ist okay, hatte die maximierung übersehen. Dualität: den Fall das beide nichtzulässig sind hatte ich glatt vergessen. Wobei Du in deinem Beispiel max 2x-y mit ensprechenden rechten Seiten o.ä. brauchst, das was da steht ist zulässig (x=y=0). Nach überlegen ist schwacher Dualitätssatz auch sinnvoll, weil er für alle x,y gilt, und nicht nur die Optimalen. Noch mal eine Umformulierung der Dualitäts/Zulässigkeitsaussagen, hoffe jetzt stimmts. Problem ist nur, dass es jetzt ziemlich lang ist, wenn da noch Interpretationen und praktische Bedeutung der Dualität reinsollen... --Grothey 14:35, 17. Jan 2006 (CET)

Hallo Grothey, ich habe noch den Fall mit der primalen und dualen Unzulässigkeit eingebaut; jetzt sollte es stimmen. Mit dem Gegenbeispiel, das keins ist, hast Du natürlich recht. Ich muß nochmal in meinen Unterlagen nachgucken, wie das Beispiel genau aussah. Gruß, -- Sdo 14:51, 17. Jan 2006 (CET)

Ich hab's wiedergefunden:

$\min \;\{x+y\;|\;x-y\leq 0,\;-x+y\leq -1,\;x,y\geq 0\}$.

Hierbei sind sowohl das primale als auch das duale LP unzulässig. -- Sdo 18:47, 17. Jan 2006 (CET)

Nachtrag: ich kann gut auf eine Erklärung der Dualvariablen als Schattenpreise verzichten. Wie Du selbst sagst, wird das tendenziell eher lang, und Hauptziel dieses Abschnittes sollte sein, klarzumachen, was Dualität überhaupt ist und warum das wichtig ist, und nicht, eine Erklärung von Dualität in allen Details zu liefern. Von mir aus könnte im Zweifelsfall auch der komplementäre Schlupf raus, wenn der Abschnitt zu lang wird. -- Sdo 23:54, 17. Jan 2006 (CET)

Hallo Grothey, bei der Überarbeitung habe ich sowohl Schattenpreise als auch den komplementären Schlupf erstmal rausgelassen, um diesen Abschnitt nicht ausufern zu lassen. -- Sdo 23:41, 29. Jan 2006 (CET)

Doppelte oder fehlende Inhalte nach der Überarbeitung

Hallo,

ich habe den Artikel gerade gründlich restrukturiert und überarbeitet. Unter anderem habe ich einige Teile aus dem Simplex-Verfahren hier eingebaut, die sich allgemein auf lineare Optimierung bezogen und nichts speziell mit dem Simplexalgorithmus zu tun hatten. Dadurch gibt es jetzt vorübergehend einige Inhaltsdoppelungen, die ich bald (zumindest teilweise) wieder beseitigen werde, wenn ich das Simplex-Verfahren überarbeite. Die Teile des Artikels, die sich auf ganzzahlige Optimierung bezogen, habe ich erstmal rausgeworfen (der Artikel heißt Lineare Optimierung) und baue sie demnächst in Ganzzahlige lineare Optimierung ein.

Gruß, -- Sdo 23:39, 29. Jan 2006 (CET)

Hallo Sdo,

Hab' mal drübergeguckt, einige kleine Änderungen vorgenommen. Einige Anmerkungen, die mir aufgefallen sind

• Zur Geschichte: Hat die ganzzahlige Optimierung in den 1950er tatsächlich schon kommerzielle Anwendungen gehabt? Speziell bei den Ölraffinerien? Irgendein spezielles Problem, an das du da denkst?
• Telekommunikation & Routing: Ich störe mich an dem im allgemeinen Fall kein anderer exakter Algorithmus bekannt: Die Beschreibung hört sich nach einen Multicommodity Network Flow Problem an; das ist nun gerade effizienter per Dijkstra (zum finden kürzester Pfade) + Column-Generation (Dantzig-Wolfe) zu lösen.
• Irgendeinen Grund für die Reihenfolge der Verfahren? Hab' Ellipsoid weiter hinten einsortiert, kann von mir aus auch ganz verschwinden, da sie eigentlich nur für die Geschichte der Inneren Punkte Verfahren interessant ist. Sollte auf alle Fälle nicht das erste genannte Verfahren sein.

Ansonsten: gute Arbeit! -- Grothey 13:09, 6. Feb 2006 (CET)

Hallo Grothey, danke für's Drübergucken (und für das Lob :-))! Zu deinen Fragen:

1. Geschichte: Das mit den Ölraffinerien hatte ich ursprünglich aus dem Simplex-Verfahren. Inzwischen habe ich auch einen Artikel von George Dantzig gefunden (Linear Programming, Operations Research 50(1):42-47, 2002), wo er schreibt: Commercial applications were begun in 1952 by Charnes, Cooper and Mellon with their (now classical) optimal blending of petroleum products to make gasoline. Applications quickly spread to other commercial areas soon eclipsed the military applications which started the field. Das bezieht sich allerdings nur auf lineare Optimierung, da hast du recht. Den Satz mit der ganzzahligen Optimierung habe ich erstmal wieder rausgenommen – laut o.g. Artikel gab es zwar vorher schon einige Untersuchungen zum TSP, aber ein systematisches Cutting-Plane-Verfahren wurde erst 1958 von Gomory entwickelt.
2. Telekommunikation: Ja, ich meinte Multicommodityflow. Aber deine Beschreibung hört sich für mich erstmal nach einem LP in Pfadformulierung an, wo die Generierung neuer Variablen ein kürzeste-Wege-Problem ist. Hast Du einen (am besten elektronisch verfügbaren) Artikel oder ein Standardbuch, wo ich mir das von dir genannten Verfahren genauer angucken kann? Wenn nicht, wäre es nett, wenn du mir noch ein paar Details dazu geben könntest – im Moment sehe ich schlichtweg nicht, wo da die Dekomposition ist. Ich gehe gerade (in der einfachsten Variante) von einem Graphen mit Punkt-zu-Punkt-Bedarfen zwischen den Knoten und Kapazitäten auf den Kanten aus, wo es darum geht, einen Fluss innerhalb der Kapazitäten zu finden, der alle Bedarfe erfüllt.
3. Reihenfolge: Die Ellipsoidmethode hatte ich quasi als Übergang zwischen theoretischer und praktischer Lösbarkeit an dieser Stelle platziert. Aber so wie jetzt ist es eigentlich noch besser, weil der Abschnitt jetzt mit einem praktisch relevanten Verfahren startet. Dann sollte die Ellipsoidmethode wahrscheinlich auch hinter die Innere-Punkte-Verfahren geschoben werden. Drinlassen würde ich sie, weil sie historisch als erstes polynomiales Verfahren bedeutsam ist. Evtl. kann der Abschnitt aber etwas gekürzt werden.
4. Könntest Du bei den Innere-Punkte-Verfahren noch ein paar Sätze zum grundsätzlichen Vorgehen und praktisch eingesetzten Varianten dieser Verfahren dazuschreiben (bei jeder Iteration Richtung und Schrittweite wählen, Predictor-Corrector-Methode, usw.)? Im Zweifelsfall kann ich mir da zwar auch noch zwei oder drei halbwegs stimmige Sätze zusammenbasteln, aber bei dem Thema kennst du dich besser aus, glaube ich.
5. Nichtlineare Optimierung: im Artikel steht aus vorherigen Versionen noch drin, dass die L.O. auch als Unterproblem in Algorithmen zur Lösung nichtlinearer Probleme verwendet wird. Kannst du etwas dazu sagen, ob das stimmt? Wenn ja: welche Verfahren sind das, und für welche Klassen nichtlinearer Probleme werden sie verwendet? Wenn du etwas dazu weißt, würde ich das gerne dazuschreiben, sonst klingt das so nach einer wilden Behauptung (die es ja im Moment auch erstmal ist).
6. Irgendwann will ich noch ein paar schöne Polyederbilder in den Artikel packen, an denen sich das Problem, die theoretische Lösbarkeit, der Simplexalgorithmus und die Innere-Punkte-Verfahren illustrieren lassen. Ich drücke mich nur im Moment davon, sie zu basteln. Es gibt wenige mathematische Gebiete, die sich so schön anschaulich interpretieren lassen. Wenn du schöne Bilder hast, immer her damit. Beim Stöbern in den Commons habe ich auf Anhieb nichts Passendes gefunden.

Schöne Grüße, -- Sdo 22:44, 6. Feb 2006 (CET)

Kommentare zum Rest kommen später, erstmal (weil ich es gerade zur Hand habe):

zu 2) Hm, das Verfahren, das ich meine relaxiert die Kapazitätsbedingungen per Lagrange-Relaxierung/Dantzig-Wolfe. Der Rest zerfällt dann in kürzeste-Wege-Probleme — ja im Prinzip so wie du es beschreibst. Hab' folgenden Artikel gefunden: Jones, Lustig, Farvolden, Powell: MCNF: The impact of formulation on decomposition, Math Prog 62 (1993) 95-117. Hat einen Abriss über Dekompositionsansätze für das Problem darin, demnach stammt die Idee ursprünglich von Tomlin [Transportation Science 5(1971)].

zu 5) Es gibt das SLP Verfahren (Sequential Linear Programming), sowas wie der hässliche Bruder des SQP: also einfach alles linearisieren, lösen, und wieder von vorne. Ist zugegebenermassen etwas obskur. Wird aber meiner Erfahrung nach praktisch viel benutzt — Firma will nichtlineares Problem lösen, hat aber nur einen Simplex Löser: also per Hand linearisieren, lösen, wieder linearisieren. Wenn das Problem einfach genug ist (d.h. keine Globalisierungsstrategie braucht) klappt das auch. Fletcher, Saintz de Maza: Nonlinear programming and nonsmooth optimization by successive linear programming, Math. Prog 43 (1989) versuchen die Idee auf sichere Füsse zu stellen.

Grüsse -- Grothey 12:34, 7. Feb 2006 (CET)

Danke, gucke ich mir mal an. -- Sdo 00:28, 8. Feb 2006 (CET)

Ich abe das zum Anlass genommen, endlich mal rauszukriegen, was D.-W.-Dekomposition eigentlich genau ist – das wollte ich schon lange wissen. Im Nemhauser/Wolsey steht das ganz gut drin, und im Ahuja/Magnanti/Orlin ist die Anwendung auf Multicommodityflow beschrieben. Das ist ja in diesem Zusammenhang wirklich nichts anderes als eine Pfadflussformulierung, die mit Column Generation gelöst wird. Da habe ich also die ganze Zeit D.W.-Dekomposition betrieben, ohne dass ich es wusste... ;-) Ich würde das aber zu den LP-basierten Verfahren zählen. Auch wenn da nicht unbedingt der Simplexalgorithmus o.ä. angeworfen wird, ist die Motivation und die Theorie dahinter doch sehr LP- und dualitätsbasiert. Mit anderer Algorithmus meinte ich wirklich kombinatorisch, also komplett unabhängig von LP-Theorie. Ich habe das im Artikel mal präzisiert. Gruß, -- Sdo 23:22, 8. Feb 2006 (CET)

Motivation für den dualen Simplex

verschoben nach Diskussion:Simplex-Verfahren, Antwort siehe dort. -- Sdo 23:31, 1. Mär 2006 (CET)

Degeneriertes lin. OptProb.?

Wann ist ein lin. Optprob degeneriert? Meine letzte Vorlesung diesbezüglich liegt schon etwas her, weshalb ich jetzt keinen Käse schreiben möchte. :) -- (Beitrag von 80.139.245.152) -- Sdo 01:10, 11. Apr 2006 (CEST)

Hallo 80.139.245.152! Ein LP ist degeneriert, wenn das zugehörige Polytop eine Ecke besitzt, die durch mehrere Basen beschrieben werden kann. Anschaulich ist das der Fall, wenn die Ecke durch mehr Ungleichungen definiert wird als minimal nötig. Beispielsweise lässt sich im dreidimensionalen Raum die obere Ecke einer Pyramide mit quadratischer Grundfläche auf vier verschiedene Arten als Schnitt von jeweils drei Facetten des Polytops darstellen. Zu der Ecke gehören also vier verschiedene Basen des zugehörigen LPs. So gut wie alle praktisch auftretenden LPs sind degeneriert. Ich hoffe, das hilft Dir weiter. Gruß, -- Sdo 01:10, 11. Apr 2006 (CEST)

Relativ innerer Punkt

Habe vor einiger Zeit den Artikel geschrieben. Die Definitionen habe ich aus online-literatur, die ich leider dort nicht verlinkt habe. Wenn meine Erinnerung, dass man das irgendwie für Optimierung braucht, stimmt, könnte das jemand mal Richtung Anwendungsbezug ausbauen und evtl. umkategorisieren? Mir fehlen da die Kenntnisse. --KleinKlio 22:45, 13. Nov. 2006 (CET)

Na ja, brauchen ist zuviel gesagt... Optimallösungen linearer Programme werden an Randpunkten und nicht an inneren Punkten angenommen. Das Simplex-Verfahren hüpft von Ecke zu Ecke, Innere-Punkte-Verfahren schleichen sich durchs Innere eines Polytops an eine Optimallösung ran und springen dann am Ende drauf (im sog. Crossover-Schritt). Ansonsten wüsste ich auf Anhieb nicht, wozu man das braucht. -- Sdo 23:52, 14. Nov. 2006 (CET)

Standardform

Ein (LOS) (lineares Optimierungsproblem in Standardform) ist ein LP von der Form
$\min\{c^{T}x|Ax=b,x\geq 0\}$
entscheidend ist vor allem die Gleichheitsbedingungen (aus denen Mann schließlich den Simplex ableitet)

ein (ALO) (allgemeines Lineares Optimierungsproblem) dagegen ist von der Form

$\min /\max\{c^{T}x|A_{1}x=b_{1},A_{2}x\leq b_{2}\}$

Ein (ALO) lässt sich in ein (LOS) übersetzen durch:
(1) \max c^Tx = \min -c^Tx
(2) Einführen von Schlupfvariablen zur Entfernung der Ungleichungen
(3) Zerglegung der Variablen in Positiv- und Negativteil zur Gewinnung der Vorzeichenbeschränkung
(4) Entfernen von lineare abhängigen Zeilen

Des weiteren muss, wie der letzte Punkt zeigt, darauf geachtet werden, dass die Matrix maximalen Rang hat (hier nicht zu verwechseln mit $detA\neq 0$, da die Matrix nicht zwingend quadratisch ist). -- (nicht signierter Beitrag von 85.212.174.128 (Diskussion) 11:55, 23. Nov. 2006)

Unter Standardform versteht jeder etwas anderes, je nachdem, was er gerade betrachtet. Das stört auch nicht, weil sich ja alle Formen ineinander überführen lassen (wie es auch im Artikel steht). Die Variante $Ax=b$ und den vollen Zeilenrang der Matrix benötigt man nur für das Simplex-Verfahren. Natürlich kann man ein LP auch allgemein mit Gleichungen und Ungleichungen aufschreiben, wie du es gemacht hast. Aber oft kann man für polyedrische Untersuchungen die Gleichungen ignorieren, alles in der Dimension des Ungleichungspolyeders betrachten und ein volldimensionales Polyeder annehmen. Dann tut es auch die Variante $Ax\leq b$, die deshalb auch in der Literatur meistens für polyedrische Betrachtungen verwendet wird. -- Sdo 12:22, 23. Nov. 2006 (CET)

Ich frage mich, ob man im Artikel zur Sicherheit erwähnen sollte, dass es (vor allem in der englischsprachigen - siehe auch en:Linear programming) in der Literatur auch die andere Definition gibt (so als Warnung). Oder ist dies als eine Selbstverständlichkeit zu betrachten, dass sowieso in jedem Buch eine andere Notation/Terminologie verwendet wird und dass es in der Verantwortung eines Lesers liegt die jeweiligen Definitionen zu überprüfen? Evotopid (Diskussion) 13:15, 14. Okt. 2016 (CEST)--

Wie Sdo erwähnt, versteht unter Standardform jeder etwas anderes, und genau das sollte im Artikel gesagt werden, ohne dass wir anfangen, jede der mehr als zwei Formen aufzuzählen. Didaktisch gesehen ist die Form $\max\{dx~|~Ax\leq b,x\geq 0\}$ bzw $\max\{dx~|~b+Gx\geq 0,x\geq 0\}$ die einfachste, und auch die Grundform für die Simplex- und andere Pivotverfahren, da sie sowohl die Existenz einer Ecke als auch den vollen Zeilenrang der Eintragsmatrix automatisch garantiert. (Es ist falsch, dass man für Simplex-Verfahren die Variante $Ax=b$ gebraucht) --Heinrich Puschmann (Diskussion) 22:39, 15. Okt. 2016 (CEST)

Ecke

Es fehlt die Definition der Ecke (nicht darstellbar als echte Konvexkombination verschiedener Punkte des Polyeders) -- (nicht signierter Beitrag von 85.212.174.128 (Diskussion) 11:55, 23. Nov. 2006)

Ich hab's verlinkt. Eine Erklärung des Begriffs habe ich jetzt nicht eingebaut, weil der Begriff Ecke in Verbindung mit dem Bild meines Erachtens anschaulich genug ist. Mathematiker können unter der Verlinkung nach der genauen Definition gucken, und Laien hilft die Erklärung mit der Konvexkombination auch nicht weiter. -- Sdo 12:22, 23. Nov. 2006 (CET)

Der Vollständigkeit halber ist es meiner Meinung nach schon wichtig. Wenn man mathematische Artikel schreibt, sollte man auch mathematische Sorgfalt walten lassen ^^. --Crus4d3r

Na gut. -- Sdo 22:00, 26. Nov. 2006 (CET)

Das Beispiel

Die Zielfunktion mit der Konstante 36.000 hat in der formalen Beschreibung des LP nichts verloren, da diese wie gesagt von der Form $c^{T}x$ ist. Auch wenn die Konstante zugegebendermaßen nichts ausmacht ist da ein formaler Fehler. -- (nicht signierter Beitrag von 85.212.174.128 (Diskussion) 11:55, 23. Nov. 2006)

Ja, das stört mich auch schon seit längerem. Ich habe das bisher nur deshalb nicht geändert, damit die Beschreibung zum Bild passt. Ich bin bisher noch nicht dazu gekommen, mal ein schöneres Bild ohne Konstante zu basteln, das gleichzeitig auch für Laien den Anwendungsbezug klarmacht. -- Sdo 12:22, 23. Nov. 2006 (CET)

Erledigt. -- Sdo 02:40, 5. Mär. 2007 (CET)

Review vom 5.–23.3.2007

Diesen Artikel hatte ich schon vor längerer Zeit gründlich überarbeitet, nachdem ich ihn wegen konfuser Struktur und fehlender Inhalte bei einer verfrühten Lesenswert-Kandidatur selbst abgelehnt hatte. Jetzt möchte ich ihn lesenswert und möglichst sogar exzellent machen. Was fehlt dazu noch? Ist der Artikel für Nichtmathematiker halbwegs verständlich? Wird der Zusammenhang zwischen linearen Programmen und Polytopen klar? Wenn nein, was kann verbessert werden? Schon mal vielen Dank, -- Sdo 03:04, 5. Mär. 2007 (CET)

Review Cactus26

Habe ehrlich gesagt Schwierigkeiten, dem Artikel zu folgen, obwohl ich mich nicht als totalen mathematischen Laien sehen würde. Allerdings habe ich wenig Ahnung von linearer Algebra, die geometrische Interpretation ist für mich "verstehbarer", wobei ich auch diese nicht ganz durchdringe. Hoffe mein Feedback ist trotzdem hilfreich:

• Innere-Punkte-Verfahren wird "artikellos" verwendet, wirkt auf mich seltsam, würde z.B. den/dem Innere-Punkte-Verfahren erwarten (dies würde z.B. auch deutlich machen, ob Plural oder Singular gemeint ist, was mir nicht klar ist). Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)
• Die "Infobox" im Artikel Vektorraum finde ich hilfreich. Könnte ich mir bei diesem Artikel auch gut vorstellen.

Die hat dort gestern jemand rausgenommen. Ich finde sie auch nur mittelmäßig schön, und eigentlich steht bei der Linearen Optimierung alles Wesentliche in den ersten paar Sätzen der Einleitung drin. -- Sdo 01:43, 10. Mär. 2007 (CET)

• Geschichte: Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)
  • was sind Ad-Hoc-Regeln? Vielleicht ein zus. erläuternder Nebensatz.
  • LR-Zerlegungen, was ist das?
  • Pivotstrategien. analog Ad-Hoc-Regeln
  • "Struktur Anzahl" würde ich mit Bindestrich schreiben
  • Die Abkürzung "LP" wird verwendet, bevor sie eingeführt ist.
• Mathematische Formulierung Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)
  • Mir würde entgegenkommen, wenn Matrix und Vektor hier verlinkt wären.
  • "Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von Ax = b durch Ax<= b und Ax>=b)"; Ist das nicht gerade falsch herum?
• Die Überschriften "Bespiel" und "Praktische Aufgabenstellung" würde ich zu einer Überschrift vereinen ("Beispiel aus der Produktionsplanung") und den einleitenden Satz weglassen. Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)
• Eine Abbildung zur Verdeutlichung dieses praktischen Beispiels (nur der Aufgabenstellung, nicht der Lösung) wäre nicht schlecht. Wenn man es verstehen will, muss man sich ein Bild malen. Aus dem Text heraus schaffen das Normalsterbliche nicht, würde ich behaupten. s.u. -- Sdo 01:43, 10. Mär. 2007 (CET)
• Der Abschnitt "Anwendungen" ist relativ leicht zu verstehen, vielleicht wäre es hilfreich, diesen weiter vorn im Artikel zu plazieren. s.u. -- Sdo 01:43, 10. Mär. 2007 (CET)
• "Komplexität und Lösungsverfahren" und "Dualität" habe ich noch nicht bearbeitet. Würde ich auch nur machen, wenn Du mein Feedback grundsätzlich hilfreich findest.

--Cactus26 08:28, 7. Mär. 2007 (CET)

Hallo Cactus, danke für diese sehr hilfreichen Hinweise! Schon mal ein paar Anmerkungen dazu:

• Innere-Punkte-Verfahren stehen ohne Artikel da, weil der Begriff eine ganze Familie von Algorithmen beschreibt. Das ist also in etwa so ein generischer Begriff wie „Iterative Verfahren zur Lösung linearer Gleichungssysteme“, wovon es auch einen ganzen Haufen gibt. Ich gucke mal, ob ich das noch klarer formulieren kann. Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)
• Eine LR-Zerlegung ist ein Verfahren zur Zerlegung einer Matrix in eine obere und eine untere Dreiecksmatrix, was die Lösung linearer Gleichungssysteme vereinfacht. Ist jetzt verlinkt; evtl. erkläre ich das im Artikel noch kurz. Verwendung sollte jetzt klarer sein, wird aber nicht im Detail erklärt. -- Sdo 01:43, 10. Mär. 2007 (CET)
• Das mit der „Struktur Anzahl“ war eine Mischung aus zwei Versionen dieses Satzes (Struktur der Matrix bzw. Anzahl und Anordnung der Nicht-Null-Elemente). Die Struktur ist jetzt raus aus dem Satz.
• Zu Gleichheits- und Ungleichheitsbedingungen: wieso falsch herum? Wenn ich Ax = b in die Standardform bringen will, muss ich jede Gleichung durch zwei Ungleichungen ersetzen (und anschließend >=- in <=-Ungleichungen ändern). Ich habe das gerade nochmal etwas umformuliert. Besser?

Tut mir leid, hier vestehe ich zu wenig, um mitreden zu können.--Cactus26

Beispiel: x = 3 ist äquivalent zu den beiden Ungleichungen (in Kombination) x <= 3 und x >= 3. Wenn ich also die Gleichung x = 3 in meinem LP habe und sie Kleiner-Gleich-Form bringen will, ersetze ich sie durch die beiden Ungleichungen x <= 3 und -x <= -3. Das ist da gemeint. -- Sdo 12:51, 9. Mär. 2007 (CET)

• Bild zum Beispiel: was für eine Art Bild schwebt Dir da vor? Das beste, was mir gerade dazu einfällt, ist eine Tabelle, die für jedes Produkt die Inputdaten und eine Art Maschinenbelegungsplan enthält. Also für Produkt 2 drei bunte Kästen nebeneinander, die mit A/B/C beschriftet sind und 2/1/3 Einheiten lang sind. Fällt Dir etwas Besseres ein?

Habe eine Skizze unter Commons:Image:LineareOptimierungBeispiel1.jpg hochgeladen.--Cactus26 08:07, 9. Mär. 2007 (CET)

Danke. -- Sdo 12:51, 9. Mär. 2007 (CET)

• Wo würdest Du die Anwendungen hinschieben? Sie direkt vor oder hinter die Geschichte zu setzen, hätte den Nachteil, dass die Definition eines LPs erst sehr spät im Artikel kommt.

Da hast Du Recht, ich hoffte, Du hättest eine Idee. Aber der Abschnitt Geschichte so weit vorn ist dem Verständnis eher abträglich und könnte viele Nicht-Mathematiker abschrecken, da dort so viele neue Begriffe eingeführt werden (müssen). Aber in der WP ist ja irgendwie Tradition die Geschichte immer vorn zu haben. Einzige Idee, die ich hätte, wäre, dass man die in der Einleitung des Artikels erwähnten Beispiel artikelintern verlinken könnte, um einem "ungeduldigen" Leser dorthin springen zu lassen.--Cactus26 08:15, 9. Mär. 2007 (CET)

Wäre es sinnvoll, den Abschnitt zwischen mathematische Definition und Beispiel zu schieben? -- Sdo 01:43, 10. Mär. 2007 (CET)

• Geometrische Interpretation: wo hakt es beim Verständnis? Ist es klar, warum die Lösungsmenge eines LPs ein konvexes Polyeder ist (oder zumindest glaubhaft, dass es so ist)?

Vom Ergebnis her verstehe ich die geometrische Interpretation schon. Mir sind eher die elementaren Sachen nicht klar, wahrscheinlich weil ich praktisch keine Ahnung von linearer Algebra habe: Also es hilft nichts, auch wenn's peinlich ist: Warum (und wie) definiert $a_{i}x=b_{i}$ eine Hyperebene? Es ist aber fraglich, ob Du den Artikel "idiotensicher" machen solltest, wenn ich genug Zeit investieren würde, könnte ich mir das ganze schon erschließen. Aber, was mir dabei noch einfällt: Der Text ist bei den Erläuterungen immer n-dimensinal, spricht von Hyperebene/Polyeder und verwendet damit 3-dim. Begriffe, die Abbildungen sind (natürlich) immer 2-dim. (Gerade, Vieleck). Vielleicht wäre das durchspielen eines 2-dim. Beispiels im Text für das Verständnis hilfreich.

Na ja, ich will den Lesern das Verständnis schon so weit wie möglich erleichtern. Ich habe gerade den Abschnitt Geometrische_Interpretation daraufhin etwas überarbeitet. Besser so? -- Sdo 12:19, 8. Mär. 2007 (CET)

Was ein konvexes Polyeder ist kann ich mir schon vorstellen, ich würde sagen, alle anderen Polyeder sind für Nicht-Mathematiker gar keine sondern nur abstrakte Gebilde (vielleicht könnte man darauf hinweisen). Werde mich morgen noch mit den restlichen Punkten auseinandersetzen.--Cactus26 07:50, 8. Mär. 2007 (CET)

• Die restlichen Hinweise sehe ich alle sofort ein und werde sie in den nächsten Tagen einbauen.

Gruß, -- Sdo 13:07, 7. Mär. 2007 (CET)

Habe nun auch die restlichen Teil des Artikels bearbeitet (aber auch Dein Feedback bearbeitet, siehe oben):

• Nochmal zur geometrischen Interpretation: Vielleicht wäre es hilfreich, die "Polyederbildung" und die Verschiebung der Lösungsgerade (-ebene) auf zwei separate Abbildungen aufzuteilen. Dann braucht man nicht auf die Farbunterscheidung der Geraden zu achten.
  So richtig glücklich bin ich mit Deiner Formulierung noch immer nicht. Ich hätte gerne eine komplette 2-dim. Betrachtung, vielleicht am Ende des Abschnitts, vielleicht so: Im nebenstehenden Bild(ern) wird die geometrische Interpretation zweidimensional dargestellt. Dabei bilden die durch die einschränkenden Ungleichungen definierten Geraden (grün) ein Vieleck, die Punkte im Inneren des Vielecks sind Lösungen des LP. Nun gilt es, eine Gerade (rot), deren Steigung vorgegeben ist, parallel möglichst weit nach rechts oben zu verschieben, so dass diese das Vieleck gerade noch berührt.

Die Formulierung ist gut, die werde ich wohl weitgehend übernehmen. Die unterschiedlichen Farben für Beschränkungen und Zielfunktion will ich aber beibehalten, da diese Geraden unterschiedliche Funktion im LP haben. -- Sdo 12:51, 9. Mär. 2007 (CET)

Nachdem ich mich gerade nochmal an der Formulierung versucht habe, gefällt mir die Auslagerung des zweidimensionalen Falls in einem Extraabsatz nicht mehr so gut. Dadurch muss ich entweder alles zweimal erklären oder der allgemeine Teil hat keinen Bezug zum Bild mehr, was das Verständnis auch nicht erleichtert. Mal sehen, wie ich das mache. Die Aufteilung auf zwei Bilder ist aber sinnvoll, glaube ich, das erledige ich noch. -- Sdo 01:43, 10. Mär. 2007 (CET)

• Noch ein Gedanke zum Beispiel: Wenn ich es richtig sehe, wäre die Lösung trivial, wenn P1 den hören DB hätte. Dann würde man ausschließlich P1 produzieren, was (fast) offensichtlich ist. Wie würde sich das denn geometrisch äußern? Vielleicht könnte man mit solchen Gedankenspielen auch eine Brücke zu "Lösbarkeit aus theoretischer Sicht" schlagen.

Geometrisch bedeutet das, dass die Zielfunktion dann steiler wäre als die Gerade $x_{1}+x_{2}\leq 150$, so dass die untere rechte Ecke eindeutige Optimallösung wäre. Interessant ist vor allem der Fall, dass beide Produkte gleichen DB haben. Dann sind alle Punkte zwischen (130,20) und (150,0) optimal. Die Idee ist gut – so einen Verweis auf das Beispiel werde ich noch bei der Lösbarkeit dazuschreiben. -- Sdo 12:51, 9. Mär. 2007 (CET) Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)

• Lösungsverfahren: Hier kann ich eigentlich ganz gut folgen, auch ohne die Hauptartikel zu verwenden. Folgende Anmerkungen:
  • was ist streng polynomial? Ist leider in Polynomialzeit nicht erläutert, würde m.E. dort hingehören.

Streng polynomial bedeutet im wesentlichen das, was in dem Halbsatz direkt danach steht. Bei allen bisher bekannten polynomialen Algorithmen für LPs geht die Größe $|a_{ij}|$ und $|b_{i}|$ der Koeffizienten in A und b in die Laufzeitabschätzung mit ein, bei einem streng polynomialen Algorithmus wäre das nicht der Fall. -- Sdo 12:51, 9. Mär. 2007 (CET)

• • Ellipsoidmethode: Hier ist mir nicht ganz klar, was der im inneren gefundene Punkt des Polyeders mit der optimalen Lösung zu tun haben soll, dass er eine Lösung ist, ist klar, aber warum optimal?

Der Trick ist folgender: Du bastelst ein neues LP, das aus dem Ursprungs-LP und seinem dualen LP besteht, zusammen mit der Bedingung, dass primaler und dualer Zielfunktionswert gleich sein sollen:

$Q:=\{(x,y)\;|\;Ax\leq b,\;x\geq 0,\;A^{T}y\geq c,\;c\geq 0,\;c^{T}x=b^{T}y\}$

Die zulässigen Punkte $(x,y)$ in $Q$ entsprechen aufgrund der Dualitätssätze genau den Optimallösungen des primal und dualen Problems. Wenn Du also einen Punkt in $Q$ gefunden hast, ist der x-Teil davon optimal für das Ursprungs-LP. Wenn es keinen solchen Punkt gibt, gibt es auch keine Optimallösung. Das wollte ich jetzt allerdings nicht im Artikel erklären, sondern das steckt im „man kann zeigen“ drin. ;-) Aber vielleicht schreibe ich noch dazu, dass die Methode auf ein anderes LP logelassen wird. -- Sdo 12:51, 9. Mär. 2007 (CET) Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)

• Dualität: Gibt es auch eine geometrische Interpretation (und ist die sinnvoll) der Abbildung des primalen auf das duale Problem?

Nein, gibt es nicht, zumindest nichts einfach Erklärbares. Das duale LP lebt im $R^{m}$, das primale im $R^{n}$. Die Abbildung ist ja im wesentlichen das Transponieren der Matrix. Erledigt. -- Sdo 01:43, 10. Mär. 2007 (CET)

--Cactus26 09:27, 9. Mär. 2007 (CET)

Review Schizoschaf

Bei den Bildern könnte deer Eindruck entstehen, dass

• (0,0) immer Teil der zulässigen Menge ist.
• x1, x2 > 0 gelten muss was aber doch nur für x', x" in der Normalform der Fall ist.

Ersterem könnte man durch Darstellung eines Allgemeineren Falls abhelfen, letzterem vielleicht durch Beschriftung der Grafiken mit x', x" und Erwähnung in der Bildunterschrift, dass eine Normalform dargestellt wird. Könnte auch quatsch sein was ich erzähle. Fasziniend, wie schnell man so einen Kram vergisst :) --schizoschaf 17:40, 7. Mär. 2007 (CET)

Du hast recht. Ich werde die Bilder bzw. den Begleittext entsprechend abändern. Gruß, -- Sdo 23:33, 7. Mär. 2007 (CET)

Zumindest teilweise erledigt. Ich muss aber nochmal genauer darüber nachdenken, welches Bild wo sinnvoll ist. -- Sdo 01:49, 10. Mär. 2007 (CET)

---

Vielen Dank für die Anregungen! Die noch offenen Punkte werde ich erledigen, wenn ich aus dem Urlaub zurück bin. -- Sdo 00:31, 23. Mär. 2007 (CET)

"Optimierungsproblem" vs. "Programm"

Mit der wörtlichen Übersetzung des englischen "program" als "Programm" habe ich ernste Probleme, denn gemeint ist ja hier immer "Optimierungsproblem". Um eine gedankliche Trennung von Problem und Lösungsverfahren zu behalten und zusätzlich die Gefahr des Missverständnisses ("Computerprogramm" oder sogar "Algorithmus") zu vermeiden, plädiere ich dafür, im Deutschen hier immer von "(Optimierungs)Problem" oder bei der Übersetzung von "programming" von "Optimierung" und nie von "Programm" oder "Programmierung" zu sprechen. --Dringlich 15:53, 23. Okt. 2007 (CEST)

Hallo Dringlich, im Prinzip gebe ich Dir recht, aber die Bezeichnung „Lineares Programm“ hat sich nun mal auch im Deutschen eingebürgert und sollte deshalb auch erklärt werden. -- Sdo 23:25, 23. Okt. 2007 (CEST)

Ja, einmal erklären, dass oft auch von "Programm" gesprochen wird, ist richtig und notwendig. Ich finde, man muss sich aber entscheiden, welches der bevorzugte Begriff ist und den dann konsequent verwenden. Das Lemma heißt schließlich aus gutem Grund "Lineare Optimierung", im Text sind die Begriffe aber bunt gemischt. --Dringlich 14:09, 24. Okt. 2007 (CEST)

Belege

Es wird im Artikel zwar Literatur angegeben, aber es werden an keiner einzigen Stelle Publikationen referenziert. Insbesondere Textstellen wie

Er wurde schon Mitte der 1940er Jahre von George Dantzig,
einem der Begründer der Linearen Optimierung, geprägt,
bevor Computer zur Lösung linearer Optimierungsprobleme
eingesetzt wurden.

schreien förmlich nach der entsprechenden Erstveröffentlichung. Ich zweifle nicht an dieser oder anderen Aussagen des Artikels, aber allein schon für die Prüfbarkeit wären noch an vielen anderen Stellen Referenzen nötig. --Drizzd 17:39, 22. Nov. 2008 (CET)

Speziell für diese Aussage habe ich mal eine Quelle eingefügt. --tsor 17:52, 22. Nov. 2008 (CET)

Hast Du vielleicht den Titel der Veröffentlichung? Ich nehme an sie wird in der Quelle referenziert? Danke. --Drizzd 18:55, 22. Nov. 2008 (CET)

Das ist ein Buch mit 565 Seiten. Wurde seinerzeit in der Uni bei einer Vorlesung als Standardwerk empfohlen. --tsor 19:31, 22. Nov. 2008 (CET)

Verstehe. Da hast Du nicht ganz unrecht. Ich habe mal zwei weitere Referenzen für Kamarkar und den Klee-Minty-Würfel eingefügt; für den Rest muss ich nochmal nachforschen, wie die ursprünglichen Paper eigentlich hießen. Wird gelegentlich nachgereicht, sobald ich dazu komme. -- Sdo 18:56, 22. Nov. 2008 (CET)

Super, danke. --Drizzd 19:35, 22. Nov. 2008 (CET)

Beispiel2

Das Beispiel ist soweit gut, und verständlich, hat aber drei Punkte die mich stören.

-Ihr solltet die Achsen im Diagramm anschreiben

-Die Erklärung der Iso-Gewinnfunktion ist wenig verstendlich, eine Formel wie man so eine Berechnet oder Geometrisch ereicht wäre super. Habe doch etwas überlegen müssen bevor ich das gesehen habe.

-Zudem wäre schön ein Satz noch schön der Erklärt wesshalb diese Funktion den Gewinn optimiert(bzw. den Gewinn in jedem Punkt definiert). Ich bin überzeugt mit diesen drei änderungen wird man die Funktionsweise viel schneller verstehen. --Wuestenschiff 19:42, 28. Nov. 2008 (CET)

Ergänzungen zur Spieltheorie

Hallo MGM08244, was hältst Du davon, Deine Ergänzungen in einen Spezialartikel auszulagern? So etwas wie Lineare Optimierung der Spieltheorie? Dieser Artikel hier ist doch eher als Übersichtsartikel angelegt, und da ist das eigentlich zu detailliert, was Du da ergänzt hast. Was meinst Du? Nicht wundern, wenn ich nicht gleich antworte; ich fahre gleich in den Urlaub und bin erst in einer Woche wieder da. Gruß, -- Sdo 21:06, 27. Dez. 2008 (CET)

Hallo Sdo! Danke für den Hinweis. Also ich hab den Artikel für das Wiwiwiki-Projekt geschrieben und da war es so angedacht den Artikel hier zu integrieren. Werde meinen Beitrag jedoch auslagern, entweder als eigenständigen Artikel oder als Unterpunkt der Gemischten Strategie. Weiß ja selber, dass die Bearbeitung doch recht umfangreich geworden ist. Liegt an den ganzen Formeln und Gleichungen...

Hättest du vielleicht noch ein paar inhaltliche Anregungen für mich? Sollte ich was kürzen oder vielleicht sogar noch weiter ausholen? Ist alles verständlich? Mach das schließlich zum ersten Mal. mfg --MGM08244 19:55, 2. Jan. 2009 (CET)

Einige Anregungen habe ich:

1. Das Zeichen zwischen $S_{2}$ und $S_{n-1}$ wird von meinem Browser (firefox-2.0.0.20) nicht dargestellt, weder im Editiermodus noch in der gerenderten Version. Stattdessen lieber \ldots bzw. \vdots verwenden.
2. Die Operatoren $\min$ und $\max$ werden normalerweise im Quelltext als \min und \max geschrieben und damit nicht kursiv gesetzt.
3. Das Ganze ist ziemlich technisch. Wenn der Text auf eine eigene Seite ausgelagert wird, sollte auf jeden Fall noch eine laienverständliche Einleitung dazu. Vielleicht ist es sinnvoll, den Teil ab Vorgehen nach Lineare Optimierung/Spieltheorie zu verlagern und im Abschnitt Spieltheorie darauf zu verweisen. Dann ist das quasi ein technischer Appendix für interessierte Leser, der auch nicht ganz soviel Extra-Einleitung benötigt, wie wenn es ein wirklich eigenständiger Artikel wäre.

Gruß, Sdo 18:30, 4. Jan. 2009 (CET)

Hallo Sdo...wie vorgeschlagen habe ich meinen Beitrag zur Spieltheorie ausgegliedert (Lineare Optimierung (Spieltheorie))! Leider konnte ich deine Anregung zur Tabelle (Auslassungspunkte über \ldots und \vdots darzustellen) nicht umsetzen. Habe jetzt schon mehrere Leute um Rat gefragt, aber keiner konnte mir weiterhelfen, weil \dots immer als Text umgesetzt wird und nicht als Punkte. Braucht man eventuell noch einen speziellen Operator? Hättest du vielleicht noch ein paar Tipps für mich, sodass mein Artikel nicht so technisch wirkt? Wäre wirklich dankbar für Hilfe! Grüße--MGM08244 20:13, 18. Jan. 2009 (CET)

Hallo MGM08244, sehr schön! So ist es wesentlich übersichtlicher, und der Übersichtsartikel verweist auf die Detaildarstellungen, wie bei den anderen Abschnitten auch. Das mit den Punkten in der Tabelle habe ich gerade mal korrigiert; wahrscheinlich fehlte der Mathe-Modus. Für weitergehende Arbeit oder ausführliches Lesen des Artikels fehlt mir leider gerade bis mindestens Ende Februar die Zeit. Wenn ich wieder Zeit habe, gucke ich gerne mal drüber. Schöne Grüße, -- Sdo 13:29, 20. Jan. 2009 (CET)

Unklare Formulierung

"* Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von $a_{i}x=b_{i}$ durch $a_{i}x\leq b_{i}$ und $-a_{i}x\leq -b_{i}$"

Diese Zeile ist unklar formuliert. Ich würde das allgemein so verstehen: nimm jede Gleichung, ersetze Istgleich durch Kleinergleich, und nimm dieselbe gleichung mal -1 und ersetze Istgleich durch Kleinergleich. Ist das so gemeint? 88.72.32.188 18:08, 16. Mär. 2009 (CET)

Gemeint ist: Ersetze $a_{i}x=b_{i}$ durch $a_{i}x\leq b_{i}$ und $a_{i}x\geq b_{i}$. Die letzte Ungleichung wurde dann noch mit (-1) multipliziert, um sie in Kleiner-Gleich-Form zu bringen. -- Sdo 09:53, 23. Mär. 2009 (CET)

Beispiel - optimale Lösung?

In dem Beispiel wird als optimale Lösung die Ecke ganz rechts genannt mit dem Funktionswert 49.000. Nach meinen Rechnungen ist die Ecke 90/60 allerdings mit 57.000 optimaler. (nicht signierter Beitrag von 84.57.225.1 (Diskussion | Beiträge) 12:42, 18. Jul 2009 (CEST))

Da muss ich dich leider enttäuschen. Die Berechnung bzw. graphische Darstellung des Beispiels ist korrekt. In deiner Überlegung hast du die Restriktion der Maschine A nicht berücksichtigt. Durch diese Restriktion ist die Basislösung (90,60) nicht zulässig.Nimruth (Diskussion) 10:49, 28. Aug. 2015 (CEST)

Einleitung

Dort findet sich: „lassen sich [...] geometrisch motivieren“. Wäre es nicht toll, solange es lediglich Motivation und nicht Motivation (Mathematik) gibt, das etwas allgemeinverständlicher auszudrücken? Mit „darstellen“ beispielsweise? --Geri, ✉ 13:17, 10. Nov. 2009 (CET)

Geschichte

Ich habe mir erlaubt, "Buch" durch "Aufsatz" zu ersetzen (denn darum handelt es sich). Gleichzeitig habe ich den Web-Link zum Aufsatz (Volltext-Version) gesetzt.--Ökonomikus 14:42, 8. Sep. 2010 (CEST)

Im Geschichtsteil wird von "LP-Matrizen" gesprochen, es fehlt eine Erklärung wofür LP steht (Lineares Programm), dies wird erst unter "Problemdefinition" erwähnt.--Harald321 (Diskussion) 17:32, 19. Jan. 2015 (CET)

Weniger ist Mehr

Ich habe den Eindruck, dass in diesem Artikel immer wieder Neues hinzugefügt wird und keiner den Mut hat, überflüssig wiedergekäutes zu entfernen. Und je mehr der Artikel wächst, desto weniger traut sich jemand, das Wichtige vom absolut Nebensächlichen zu trennen. Aber vielleicht ist das ein allgemeines Wikipedia-Problem; ich wollte nur darauf hinweisen und werde nicht böse, wenn jemand meine letzte Tilgung rückgängig macht :-)

Die Beschreibung leicht verschiedener Formulierungsvarianten halte ich deshalb für so öde, weil ihr jede Begründung fehlt (Vorkommen in Textbüchern ist keine stichhaltige Begründung). Ihren Sinn finden diese Formulierungen meistens nur für irgendeinen Algorithmus (zB Simplex), weshalb die Formulierung -soweit nötig- im Artikel mit dem Algorithmus stehen sollte und nicht hier. Und wieweit sind die Namen dazu Standard? Um zu belegen, das eine Benennung Standard ist, genügt nicht ein einzelnes Textbuch, die widersprechen sich manchmal.

Noch ein Fall ist das Kapitel "Anwendungen der Linearen Optimierung", es gehört voraussichtlich ausgelagert, da die möglichen Anwendungen so viele sind, dass sie den Artikel ganz überwuchern würden. Ein Einzelbeispiel genügt vollauf; schließlich werden im Artikel "Lineares Gleichungssystem" auch keine Anwendungen derselben aufgeführt.

--Heinrich Puschmann (Diskussion) 14:36, 29. Aug. 2013 (CEST)

Unendlich viele Lösungen => Zielfunktion parallel

Meiner Meinung nach stimmt es nicht, dass die Zielfunktion parallel zu einer beschränkenden Hyperebene sein muss, wenn es unendlich viele Lösungen gibt.

1. Die Formulierung ist unglücklich: Was bedeutet Parallelität einer Funktion und einer Hyperebene. Fasst man die Zielfunktion als Vektor auf, was bedeutet dann Parallelität eines Vektors und einer Hyperebene. Gemeint ist wahrscheinlich Parallelität der Niveauhyperebenen und einer begrenzenden Hyperebene (oder äquivalent des Kerns der Zielfunktion und einer begrenzenden Hyperebene).
2. Gegenbeispiel: Betrachte das lineare Programm im $\mathbb {R} ^{3}$:

$\min\{x_{1}+x_{2}:x_{1},x_{2},x_{3}\in [0,1]\}$,

in dem die Summe der ersten beiden Variablen in einem Würfel der Seitenlänge 1 minimiert werden soll. Die Menge der Optimallösung ist die Kante mit $x_{1}=x_{2}=0,\ x_{3}\in [0,1]$, also insbesondere gibt es unendlich viele Optimallösungen, aber die Niveauebenen der Zielfunktion sind offenbar nicht parallel zu den Ebenen des Würfels. --Maformatiker (Diskussion) 17:17, 23. Jan. 2016 (CET)

Und wenn man mal andersherum fragt: Wenn es unendlich viele Lösungen gibt, was bedeutet das dann? Und wann kann das überhaupt vorkommen? --DWI (Diskussion) 17:35, 23. Jan. 2016 (CET)

Anschaulich bedeutet das, dass eine Kante (und nicht eine Hyperebene) des zulässigen Bereichs parallel zu (dem Kern) der Zielfunktion ist (in dem Sinne, dass man die Kante so verschieben kann, dass sie im Kern der Zielfunktion liegt) oder anders ausgedrückt, dass eine Kante in der Niveauhyperebene der Zielfunktion liegt, wenn man als Niveau den optimalen Zielfunktionswert nimmt. Eine notwendige algebraische Bedingung hierfür ist meiner Meinung, dass es n-1 linear unabhängige Zeilen der Nebenbedingungsmatrix (in $\leq$-Form) gibt, so dass die diese zusammen mit dem Zielfunktionsvektor linear abhängig sind (in dem Beispiel haben wir die Zeilen (1,0,0) und (0,1,0), die linear unabhängig sind, aber (1,0,0), (0,1,0) und (1,1,0) sind linear abhängig). Diese algebraische Bedingung ist aber wohl nicht hinreichend. --Maformatiker (Diskussion) 19:04, 23. Jan. 2016 (CET)

Problemdefinition - Mathematische Formulierung

dritter Stichpunkt: (Gleichheitsbedingungen statt Ungleichheitsbedingungen) falschherum aufgeschrieben? Müßte heißen: Ersetzung von a_i*x<=b_i bzw. a_i*x>=b_i durch a_i*x=b_i. Aber ich frage mich, ob sich das Ganze dann noch in die Standardform überführen lässt. (nicht signierter Beitrag von 77.180.165.11 (Diskussion) 15:42, 30. Jan. 2016 (CET))

Das sollte schon so passen. Im Artikel ist die Standardform mit $\leq$, also werden Gleichungen durch Ungleichungen mit $\leq$ ersetzt. Grüße -- HilberTraum (d, m) 17:26, 30. Jan. 2016 (CET)

Fomulierung von Problemen als Lineare Programme

Es ist durchaus möglich, dass ich hier den Wald vor lauter Bäumen einfach nicht sehe... falls dem jedoch nicht der Fall sein sollte, so würde ich gerne folgendes anmerken:
Während der Artikel die theoretische Perspektive bereits äußerst umfassend abdeckt, fände ich einen einen Abschnitt wünschenswert, der sich mit linearen Programmen und LP-Solvern in der Praxis auseinandersetzt.
So sind z.B. viele LP-Solver frei verfügbar, während dagegen die Hochleistungstiere so teuer sind, dass sie die Möglichkeit anbieten, sich auf Stundenpreisbasis/Rechner mieten zu lassen.
Da die lineare Optimierung bereits äußerst gründlich studiert wurde, können die LP-Solver für den Nutzer auch die meisten theoretischen Aspekte übernehmen.

Nichtsdestotrotz ist und bleibt die grundlegende Modellierung wohl für absehbare Zeit Aufgabe des Nutzers, so dass Faustregeln, Tricks und derartiges ebenfalls äußerst hilfreich wären, z.B.:
Was sind meine Variablen beim Optimieren?
Einführen von künstlichen Variablen, um komplexere, durch die Ungleichungen dargestellte Sachverhalte in die zu minimierende Funktion einzubringen (z.B. hier: Lineare Regression - Minimierung der maximalen Distanz)
Formulierung des LP mit Blick auf die Laufzeit
Wie man (begrenzt) Funktionen in LP's verwenden kann, die eigentlich gar nicht linear sind (Die Betragsfunktion in LP's) Sanitiy (Diskussion) 01:30, 27. Mai 2019 (CEST)